#!/usr/bin/env python3
import sys
import re

def inc(dictionary, key):
    try:
        dictionary[key] += 1
    except KeyError:
        dictionary[key] = 1

polymer = {}
template = input()
for p in template:
    inc(polymer, p)

rules = {}
for line in sys.stdin:
    if line == '\n': continue
    source, target = [ group for group in re.match(r'([a-zA-Z]{2}) -> ([a-zA-Z])', line).groups() ]
    rules[source] = target

for i in range(int(sys.argv[1]) if len(sys.argv) > 1 else 16):
    template_new = []
    prev = template[0]
    template_new.append(prev)
    for c in template[1:]:
        insertion = rules[prev + c]
        inc(polymer, insertion)
        template_new.append(insertion)
        template_new.append(c)
        prev = c
    print(f'at step {i}: {template} -> {"".join(template_new)} {polymer}')
    template = ''.join(template_new)

l = min([polymer[p] for p in polymer.keys()])
m = max([polymer[p] for p in polymer.keys()])
print(f'the most common element ({m}) minus the least common element ({l}) yields a difference of {m - l}')